package com.test.daily.leetcode.y2022.m07.day0701.v03;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Tom on 2022/7/2
 */
public class Solution {
    public static class Edge{
        int from;
        int to;
        int available;
        public Edge(int a, int b, int c){
            from = a;
            to = b;
            available = c;
        }
    }
    public static class Dinic{
        int N;
        static ArrayList<Edge> edges;
        ArrayList<ArrayList<Integer>> nexts;
        static int[] cur;
        static int[] depth;
        public Dinic(int num){
            N = num + 1;
            cur = new int[N];
            depth = new int[N];
            edges = new ArrayList<>();
            nexts = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                nexts.add(new ArrayList<>());
            }
        }
        public void addEdge(int u , int v, int r){
            int m = edges.size();
            edges.add(new Edge(u, v, r));
            nexts.get(u).add(m);
            edges.add(new Edge(v, u, 0));
            nexts.get(v).add(m+1);
        }

       public boolean bfs(int s, int t){
            LinkedList<Integer> queue = new LinkedList<>();
            boolean[] visited = new boolean[N];
            queue.addFirst(s);
            visited[s] = true;
            while(!queue.isEmpty()){
                int u = queue.pollLast();
                for (int i = 0; i < nexts.get(u).size(); i++) {
                    Edge e = edges.get(nexts.get(u).get(i));
                    int v = e.to;
                    if(!visited[v] && e.available > 0){
                        visited[v] = true;
                        depth[v] = depth[u] + 1;
                        if(v == t){
                            break;
                        }
                        queue.addFirst(v);
                    }
                }
            }
            return visited[t];
       }
        public  int dfs(int s, int t, int r){
            if(s == t || r == 0){
                return r;
            }
            int flow = 0;
            int f = 0;
            for(; cur[s] < nexts.get(s).size(); cur[s]++){
                int ei = nexts.get(s).get(cur[s]);
                Edge e = edges.get(ei);
                Edge o = edges.get(ei^1);
                if(depth[ei] == depth[s] + 1 && (f = dfs(ei, t, Math.min(r, e.available))) != 0){
                    flow += f;
                    e.available -= f;
                    o.available += f;
                    r -= f;
                    if(r < 0){
                        break;
                    }
                }
            }
            return flow;
        }
    }
}
